Volume rendering is an important branch of computer graphics, following behind the development of geometric rendering and pixel rendering. Volume rendering refers to the direct rendering of a volume data set, also referred to as a "volume," to show the characteristics of the interior of a solid object when displayed on a 2D graphics device. A volume data set is a three-dimensional array of voxels. These voxels typically are organized on a regular gridded lattice. Voxels have been defined as sample points separated by a finite distance. Each voxel has a position and a value. The voxel position is a three-tuple specifying an x, y, and z position within the 3D voxel array. The voxel value depends upon its format. For example, a voxel may have an intensity element and an index element. These elements are usually treated differently in the volume rendering process. The collection of values for all points in the volume is called a scalar field of the volume.
Volume data sets can be generated by numerous means, but most commonly by some method of 3D scanning or sampling and by numerical modeling. For example, a volume data set may be generated by Magnetic Resonance Imaging, or MRI, wherein the density of human or animal tissue is computed at each point of a 3D grid. A display of this information could indicate the boundaries of the various types of tissue, as indicated by density changes. Volume rendering is the process of displaying this data on a 2D graphics device.
The coordinate system of the volume is referred to as the source space. The very first voxel in a volume data set in source space has coordinates (x.sub.0,y.sub.0,z.sub.0) wherein x.sub.0, y.sub.0, and z.sub.0 represent the lowermost value of all x, y, and z positions in the volume data set, and is considered to be the origin of the volume data set. Normally the coordinates for this origin voxel are set to (0,0,0). The three coordinates, in order, correspond to the column, row, and slice of the image in the volume data set. The very last voxel in a volume data set is located on the opposite diagonal corner from the origin source voxel of the volume data set. Its coordinates are designated as (x.sub.u,y.sub.u,z.sub.u) wherein x.sub.u, y.sub.u, and z.sub.u, represent the uppermost values of all x, y, and z positions in the volume data set.
Volume data sets can be quite large and thus can place a strain on computer system resources. For example, a typical MRI scanner volume data set may contain 6.7 million voxels or more, whereas polygon data sets for geometric rendering typically contain less than 1/2 million polygons. Thus, there is a much greater need for special purpose hardware acceleration when rendering volumes. Special graphics hardware is designed to execute graphics algorithms very fast, much faster than the processor in a typical computer workstation. On chip cache is RAM that resides physically on the graphics hardware chip or processor chip. On chip RAM is much cheaper than external RAM and performs much faster.
In volume rendering there is often a need to be able to view the rendered image from various projections. The coordinate system of the viewer is referred to as view space or image space. It describes from which direction the volume data set is viewed and rendered. Thus, a key step in the volume rendering process is the 3D spatial volume transformation of the original volume data set from source space to view space. Typical types of transformations required may include zoom, pan, rotation, and even shear of the input volume for projection into an output raster type display device. Once a transformation has been done, various resampling techniques must be applied, such as nearest neighbor or trilinear interpolation in addition to other steps in the volume rendering pipeline, to determine pixel values for rendering.
A ray is an imaginary line emanating from a pixel on an image plane that passes through the volume. On this ray discrete steps are taken and at each step sample points along the ray are interpolated. Sample points along the ray from the image plane to the volume do not contribute to the rendered image, as well as sample points along the ray after the ray exits the volume. Depending on the view desired by the user, some rays may not pass through the volume at all and thus contribute nothing to the rendered image. Conventional volume rendering implementations typically process all sample points along a ray whether the ray passes through the volume or not or whether the sample points along the ray are within the volume or not. These implementations often require hardware solutions to check and keep track of where sample points fall. Thus, much time and system resources are wasted in the rendering process in checking and keeping track of sample points that are not needed for rendering the image. This slows down greatly the rendering process and requires costly expenditures for hardware.
Volume rendering is a very computation intensive technique. Only the most powerful super-computers of today are able to achieve reasonable rendering speeds. One of the bottlenecks in achieving reasonable rendering speeds is the organization and retrieval of the volume data set in main memory. Volume data sets are viewed as a data structure consisting of a stack of slices, or images, that are two dimensional. The normal and natural way of working with a volume data set is on a slice by slice basis.
However, each slice contains a large number of voxels. A typical volume rendering algorithm will, at a minimum, need to work with three slices at a time. This is because voxels that lie next to each other in the volume data set reside on different slices. The amount of voxels in three slices will typically exceed any data storage size for on chip cache that is feasible today. These voxels that lie next to each other through consecutive slices are not stored linearly in memory, which also breaks cache efficiency. In addition, working with slices makes it impractical to select the slice as containing desired or non-desired data, since the slice spans the entire width and height of the volume data set. In most situations nearly every slice will contain some voxels of interest.
There is a need in the art for an improved method of volume rendering that is cache efficient in respect to data organization. There is also a need in the art to only process desired data from a volume data set to speed up rendering time. There is a further need in the art for a method that does not require external RAM in the graphics hardware but can utilize small on chip RAM instead. A further need in the art is for a method that does not process volume data sets on a slice by slice basis, which is not cache efficient, nor graphics hardware efficient. There is also a need in the art to be able to store volume data sets linearly on a storage medium, such as in memory or on disk, and in small enough sizes to utilize cache without thrashing it. A further need in the art is for a volume rendering method that will call up a volume data set from memory or disk and process it only once to speed up rendering time. It is thus apparent that there is a need in the art for an improved method of data organization for volume rendering which solves the objects of the invention. The present invention meets these needs.
This application is related to: application Ser. No. 08/866,859 of Shaz Naqvi, Barthold Lichtenbelt, and Russell Huonder filed on May 30, 1997 entitled Fixed-Point Method for Fast and Precise 3D Spatial Transformations; application Ser. No. 08/865,756 of Shaz Naqvi, Russell Huonder, and Barthold Lichtenbelt filed on May 30, 1997 entitled Ray Transform Method for a Fast Perspective View Volume Rendering; and application Ser. No. 08/866,584 of Barthold Lichtenbelt, Shaz Naqvi, and Tom Malzbender filed on May 30, 1997 entitled A Volumetric Pre-Clipping Method That Guarantees Minimal Number of Sample Points Through a Volume, which are incorporated herein by reference for all that is disclosed and taught therein.